// https://leetcode.cn/problems/as-far-from-land-as-possible/

// 题干：你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。
//      其中 0 代表海洋，1 代表陆地。
//      请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，
//      并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
//      我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

// 示例：输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
//      输出：2

// 碎语：跟01矩阵没有很大的差别

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};
    typedef pair<int, int> PII;
public:
    int maxDistance(vector<vector<int>>& grid)
    {
       // 0是海洋，1是陆地
       queue<PII> q;
       int m = grid.size(), n = grid[0].size();
       bool vis[m][n]; memset(vis, 0, sizeof(vis));
       bool isUnique[2] = {0};

       for (int i = 0 ; i < m ; i++){
           for (int j = 0 ; j < n ; j++){
               if (!grid[i][j]) isUnique[0] = 1;
               if (grid[i][j]){
                   isUnique[1] = 1;
                   q.push({i, j});
                   vis[i][j] = true;
               }
           }
       }
       if (!isUnique[0] || !isUnique[1]) return -1;

        int step = 0;
        while (q.size()){
            step++;
            int sz = q.size();

            while (sz--){
                auto [a, b] = q.front();
                q.pop();

                for (int k = 0 ; k < 4 ; k++){
                    int x = a + dx[k], y = b + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]){
                        vis[x][y] = true;
                        grid[x][y] = step;
                        q.push({x, y});
                    }
                }
            }
        }

        int ret = 0;
        for (int i = 0 ; i < m ; i++){
            for (int j = 0 ; j < n ; j++){
                ret = max(ret, grid[i][j]);
            }
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> grid = {{1, 0, 1}, {0, 0, 0}, {1, 0, 1}};

    cout << sol.maxDistance(grid) << endl;

    return 0;
}